package com.yiwenup.struct._05_unionfind;

import com.yiwenup.sample.Student;
import com.yiwenup.struct._05_unionfind.base.UnionFind;

public class Main {

    public static void main(String[] args) {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
//        test6();
        GenericQuickUnion<Student> uf = new GenericQuickUnion<>();
        Student stu1 = new Student(1, "jack");
        Student stu2 = new Student(2, "rose");
        Student stu3 = new Student(3, "jack");
        Student stu4 = new Student(4, "rose");

        uf.initSet(stu1);
        uf.initSet(stu2);
        uf.initSet(stu3);
        uf.initSet(stu4);

        uf.union(stu1, stu2);
        uf.union(stu3, stu4);

        System.out.println(uf.isSame(stu1, stu2));
        System.out.println(uf.isSame(stu3, stu4));
        System.out.println(uf.isSame(stu1, stu3));

        uf.union(stu1, stu3);

        System.out.println(uf.isSame(stu1, stu3));
    }

    private static void test6() {
        UnionFind qf = new QuickUnionV5(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(2, 7));

        qf.union(4, 6);
        System.out.println(qf.isSame(2, 7));
    }

    private static void test5() {
        UnionFind qf = new QuickUnionV4(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(2, 7));

        qf.union(4, 6);
        System.out.println(qf.isSame(2, 7));
    }

    private static void test4() {
        UnionFind qf = new QuickUnionV3(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(2, 7));

        qf.union(4, 6);
        System.out.println(qf.isSame(2, 7));
    }

    private static void test3() {
        UnionFind qf = new QuickUnionV2(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(2, 7));

        qf.union(4, 6);
        System.out.println(qf.isSame(2, 7));
    }

    private static void test2() {
        UnionFind qf = new QuickUnionV1(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(2, 7));

        qf.union(4, 6);
        System.out.println(qf.isSame(2, 7));
    }

    private static void test1() {
        UnionFind qf = new QuickFind(12);
        qf.union(0, 1);
        qf.union(0, 3);
        qf.union(0, 4);
        qf.union(2, 3);
        qf.union(2, 5);

        qf.union(6, 7);

        qf.union(8, 10);
        qf.union(9, 10);
        qf.union(9, 11);

        System.out.println(qf.isSame(0, 6));
        System.out.println(qf.isSame(0, 5));

        qf.union(4, 6);
        System.out.println(qf.isSame(0, 6));
    }
}
